package com.algorithm.lesson_04;

import java.util.LinkedList;

public class ExpressionCompute {
	public static int getValue(String exp) {
		return value(exp.toCharArray(), 0)[0];
	}

	public static int[] value(char[] str, int i) {
		LinkedList<String> que = new LinkedList<String>();
		int pre = 0;
		int[] bra = null;
		while (i < str.length && str[i] != ')') {
			if (str[i] >= '0' && str[i] <= '9') {
				pre = pre * 10 + str[i++] - '0';
			} else if (str[i] != '(') {
				addNum(que, pre);
				que.addLast(String.valueOf(str[i++]));
				pre = 0;
			} else {
				bra = value(str, i + 1);
				pre = bra[0];
				i = bra[1] + 1;
			}
		}
		addNum(que, pre);
		return new int[] { getNum(que), i };
	}

	public static void addNum(LinkedList<String> que, int num) {
		if (!que.isEmpty()) {
			int cur = 0;
			String top = que.pollLast();
			if (top.equals("+") || top.equals("-")) {
				que.addLast(top);
			} else {
				cur = Integer.valueOf(que.pollLast());
				num = top.equals("*") ? (cur * num) : (cur / num);
			}
		}
		que.addLast(String.valueOf(num));
	}

	/**
	 * 计算只含加减和数字的表达式的值
	 * 
	 * @param que
	 *            只含"+","-","num":例如3+10-8
	 */
	public static int getNum(LinkedList<String> que) {
		int res = 0;
		boolean add = true;// 判断当前操作是否为+的标记
		while (!que.isEmpty()) {
			String cur = que.pollFirst();
			if (cur.equals("+")) {
				add = true;
			} else if (cur.equals("-")) {
				add = false;
			} else {
				// 结算当前结果
				int num = Integer.valueOf(cur);
				res += add ? num : (-num);
			}
		}

		return res;
	}
}
